/**
 * @brief 单链表的模板类
 * @author TMJ
 * @date 2023-12-22
 * @version 1.0
 */

#ifndef SINGLE_LINKED_LIST_H
#define SINGLE_LINKED_LIST_H

#include <new>
#include <iostream>
#include "linear_list.h"

// 链表结点结构
template<typename type>
struct LinkNode {

    LinkNode() : next(nullptr) {}

    LinkNode(const type &data, LinkNode<type> *next = nullptr) : data(data), next(next) {}

    type data;            // 数据域
    LinkNode<type> *next; // 指针域
};

// 链表结构
template<typename type>
class SingleLinkedList
        : public LinearList<type> {
public:

    // 默认构造函数
    SingleLinkedList();

    // 拷贝构造函数
    SingleLinkedList(const SingleLinkedList<type> &srcList);

    // 析构函数
    ~SingleLinkedList();

    // 清空链表
    void clear();

    // 获取链表头指针
    LinkNode<type> *getHead() const;

    // 获取指定位置的结点
    LinkNode<type> *getNode(int pos) const;

    // 查找指定元素
    LinkNode<type> *search(type data);

    // 插入结点
    bool insertNode(int pos, LinkNode<type> *node);

    // 获取链表长度
    int getLength() const;

    // 获取指定位置的信息
    bool getData(int pos, type &data) const;

    // 设置指定位置元素的值
    bool setData(int pos, const type &data) const;

    // 插入元素
    bool insertData(int pos, const type &data);

    // 移除元素
    bool removeData(int pos, type &data);

    // 判断是否为空
    bool isEmpty() const;

    // 打印链表
    void print();


private:

    LinkNode<type> *_head;  // 头指针
    int _length;  // 链表长度

};

/**
 * 默认构造函数
 * @tparam type 数据类型
 */
template<typename type>
SingleLinkedList<type>::SingleLinkedList() {
    this->_head = new LinkNode<type>();
    if (!this->_head) {
        throw std::bad_alloc();
    }
    this->_length = 0;
}

/**
 * 拷贝构造函数
 * @tparam type 数据类型
 * @param srcList 源链表
 */
template<typename type>
SingleLinkedList<type>::SingleLinkedList(const SingleLinkedList<type> &srcList) {
    this->_head = new LinkNode<type>();
    if (!_head) {
        throw std::bad_alloc();
    }

    this->_length = srcList._length;

    LinkNode<type> *destMove = this->_head;
    LinkNode<type> *srcMove = srcList._head->next;

    while (srcMove) {
        destMove->next = new LinkNode<type>(srcMove->data);
        destMove = destMove->next;
        srcMove = srcMove->next;
    }
}

/**
 * 析构函数
 * @tparam type 数据类型
 */
template<typename type>
SingleLinkedList<type>::~SingleLinkedList() {
    this->clear();
    delete this->_head;
}

/**
 * 获取链表长度
 * @tparam type 数据类型
 * @return 链表长度
 */
template<typename type>
int SingleLinkedList<type>::getLength() const {
    return this->_length;
}

/**
 * 获取指点位置的数据
 * @tparam type 数据类型
 * @param pos 指定位置（1序）
 * @param data 返回的数据
 * @return 操作是否成功
 */
template<typename type>
bool SingleLinkedList<type>::getData(int pos, type &data) const {
    // 非法性检测
    if (pos <= 0 || pos > this->_length) {
        return false;
    }

    int index = 0;
    LinkNode<type> *cur = this->_head;
    while (index != pos) {
        cur = cur->next;
        ++index;
    }
    data = cur->data;

    return true;
}

/**
 * 设置指定位置的结点的值
 * @tparam type 数据类型
 * @param pos 指定位置（1序）
 * @param data 修改后的数据值
 * @return 操作是否成功
 */
template<typename type>
bool SingleLinkedList<type>::setData(int pos, const type &data) const {
    // 非法性检测
    if (pos <= 0 || pos > this->_length) {
        return false;
    }

    int index = 0;
    LinkNode<type> *cur = this->_head;

    while (index != pos) {
        cur = cur->next;
        ++index;
    }
    cur->data = data;

    return true;
}

/**
 * 在指定位置插入元素
 * @tparam type 数据类型
 * @param pos 指定的位置
 * @param data 要插入元素的值
 * @return 操作是否成功
 */
template<typename type>
bool SingleLinkedList<type>::insertData(int pos, const type &data) {
    // 非法性检测
    if (pos <= 0 || pos > this->_length + 1) {
        return false;
    }

    // 构造新节点
    auto *newNode = new LinkNode<type>(data);
    if (!newNode) {
        return false;
    }

    // 寻找指定位置
    LinkNode<type> *front = this->_head;
    LinkNode<type> *cur = this->_head->next;
    int index = 1;

    while (index != pos) {
        front = front->next;
        cur = cur->next;
        index++;
    }

    // 插入新节点
    front->next = newNode;
    newNode->next = cur;
    this->_length++;

    return true;
}

/**
 * 删除指定位置的元素
 * @tparam type 数据类型
 * @param pos 指定位置
 * @param data 删除的元素值
 * @return 操作是否成功
 */
template<typename type>
bool SingleLinkedList<type>::removeData(int pos, type &data) {
    // 非法性检测
    if (pos <= 0 || pos > this->_length) {
        return false;
    }

    // 查找指定位置
    int index = 1;
    LinkNode<type> *front = this->_head;
    LinkNode<type> *cur = this->_head->next;

    while (index != pos) {
        cur = cur->next;
        front = front->next;
        index++;
    }

    // 删除指定结点
    data = cur->data;
    front->next = cur->next;
    delete cur;
    this->_length--;

    return true;
}

/**
 * 判断链表是否为空
 * @tparam type 数据类型
 * @return 为空 -- true 否则 -- false
 */
template<typename type>
bool SingleLinkedList<type>::isEmpty() const {
    if (this->_length == 0) {
        return true;
    }

    return false;
}

/**
 * 打印链表
 * @tparam type 数据类型
 */
template<typename type>
void SingleLinkedList<type>::print() {
    if (this->_head->next == nullptr) {
        std::cout<<"Empty list"<<std::endl;
        return;
    }

    // ----- II 非空链表打印 -----

    LinkNode<type>* cur = getHead()->next;
    while (cur != nullptr) {
        std::cout << cur->data << " ";
        cur = cur->next;
    }

    std::cout << std::endl;
}

/**
 * 清空链表
 * @tparam type 数据类型
 */
template<typename type>
void SingleLinkedList<type>::clear() {
    LinkNode<type> *cur = this->_head->next;
    while(cur) {
        this->_head->next = cur->next;
        LinkNode<type> *del = cur;
        cur = cur->next;
        delete del;
        this->_length--;
    }
}

/**
 * 获取链表结点指针
 * @tparam type 数据类型
 * @return 头节点指针
 */
template<typename type>
LinkNode<type> *SingleLinkedList<type>::getHead() const {
    return this->_head;
}

/**
 * 获取指定位置的结点
 * @tparam type 数据类型
 * @param pos 指定位置
 * @return 指定位置的结点
 */
template<typename type>
LinkNode<type> *SingleLinkedList<type>::getNode(int pos) const {
    if (pos <= 0 || pos > this->_length) {
        throw std::invalid_argument("参数异常!");
    }

    LinkNode<type> *cur = this->_head;
    int index = 0;

    while (index != pos) {
        cur = cur->next;
        index++;
    }

    return cur;
}

/**
 * 查找指定元素
 * @tparam type 数据类型
 * @param data 要查找的值
 * @return 找到结点
 */
template<typename type>
LinkNode<type> *SingleLinkedList<type>::search(type data) {
    LinkNode<type> *cur = this->_head->next;

    while (cur) {
        if (cur->data == data) {
            break;
        }
        cur = cur->next;
    }

    return cur;
}

/**
 * 在指定位置插入结点
 * @tparam type 数据类型
 * @param pos 指定的位置
 * @param node 要插入的结点
 * @return 操作是否成功
 */
template<typename type>
bool SingleLinkedList<type>::insertNode(int pos, LinkNode<type> *node) {
    // 非法性检测
    if (pos <= 0 || pos > this->length + 1) {
        return false;
    }

    int index = 1;
    LinkNode<type> *front = this->_head;
    LinkNode<type> *cur = this->_head->next;

    while (index != pos) {
        front = front->next;
        cur = cur->next;
        index++;
    }

    front->next = node;
    node->next = cur;
    this->_length++;

    return true;
}

#endif